The structural incidence problem for cartesian products

Abstract: We prove new structural results for point-line incidences. An incidence is a pair of one point and one line, where the point is on the line. The Szemer\'{e}di-Trotter theorem states that $n$ points and $n$ lines form $O(n^{4/3})$ incidences. This bound has been used to obtain many results in combinatorics, number theory, harmonic analysis, and more. While the Szemer\'{e}di-Trotter bound has been known for several decades, the structural problem remains wide-open. This problem asks to characterize the point-line configurations with $\Theta(n^{4/3})$ incidences. We prove that when the point set $\mathcal{P}$ is a Cartesian product where only one axis of it behaves like a lattice, the line set must contain many families of parallel lines to achieve the maximal incidence bound.

Theorem: Consider $1/3<\alpha<2/3$. Let $A,B\subset\RR$ satisfy that $A=\{1,2,\cdots, n^{\alpha}\}$ and $|B|=n^{1-\alpha}$. Let $\mathcal{L}$ be a set of $n$ lines in $\RR^2$, such that $I(A\times B,\mathcal{L})=\Theta(n^{4/3})$. Then $\mathcal{L}$ contains $\Omega(n^{1-\beta}/\log n)$ disjoint families of $\Theta(n^{\beta})$ parallel lines for $1-2\alpha\le\beta\le 2/3$.

When $\alpha<1/3$ or $\alpha>2/3$, it is impossible to have $\Theta(n^{4/3})$ incidences. We also completely characterize the line set when the point set is a lattice.

Joint work with Adam Sheffer. \\

number theory

Audience: researchers in the discipline

Combinatorial and additive number theory (CANT 2022)